package JianZhiOffer;

public class fib {

    public int fib(int n) {
//        if (n <= 1) {
//            return n;
//        } else {
//            return fib(n - 1) + fib(n - 2);
//        }

        // 官方看不懂
//        int a = 0, b = 1, sum;
//        for(int i = 0; i < n; i++){
//            sum = (a + b) % 1000000007;
//            a = b;
//            b = sum;
//        }
//        return a;

        if (n == 0 || n == 1) {
            return n;
        }
        int a = 0, b = 1, sum = a + b;
        for (int i = 2; i < n; i++) {
            a = b;
            b = sum;
            sum = (a + b) % 1000000007;
        }
        return sum;
    }
}
